#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int minDistance(string word1, string word2) {
	vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
	for (int i = 0; i <= word1.size(); i++)
	{
		dp[i][0] = i;
	}
	for (int i = 0; i <= word2.size(); i++)
	{
		dp[0][i] = i;
	}
	for (int i = 1; i <= word1.size(); i++)
	{
		for (int j = 1; j <= word2.size(); j++)
		{
			if (word1[i - 1] == word2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1];
			}
			else
			{
				dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i - 1][j - 1] + 2, dp[i][j - 1] + 1));
			}
		}
	}
	return dp[word1.size()][word2.size()];
}


int minDistance1(string word1, string word2) {
	vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
	for (int i = 0; i <= word1.size(); i++)
	{
		dp[i][0] = i;
	}
	for (int j = 0; j <= word2.size(); j++)
	{
		dp[0][j] = j;
	}
	for (int i = 1; i <= word1.size(); i++)
	{
		for (int j = 1; j <= word2.size(); j++)
		{
			if (word1[i - 1] == word2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1];
			}
			else
			{
				dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
			}
		}
	}
	return dp[word1.size()][word2.size()];
}


int countSubstrings(string s) {
	vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
	int count = 0;
	for (int i = s.size() - 1; i >= 0; i--)
	{
		for (int j = i; j<s.size(); j++)
		{
			if (s[i] == s[j])
			{
				if (j - i <= 1 || dp[i + 1][j - 1])
				{
					count++;
					dp[i][j] = true;
				}
			}
		}
	}
	return count;
}

int longestPalindromeSubseq(string s) {
	vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
	for (int i = 0; i < s.size(); i++)
	{
		dp[i][i] = 1;
	}
	for (int i = s.size() - 1; i >= 0; i--)
	{
		for (int j = i + 1; j < s.size(); j++)
		{
			if (s[i] == s[j])
			{
				dp[i][j] = dp[i + 1][j - 1] + 2;
			}
			else
			{
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[0][s.size() - 1];
}

int main()
{
	string s = "bbbab";
	cout << longestPalindromeSubseq(s) << endl;
	return 0;
}